#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
#include <cstdio>
#include <cassert>
#include <list>
#include <map>
#include <string>
#include <ctime>
#include <cstring>
using namespace std;

class BigInteger
{
	enum
	{
		N = 10000
	};
public:
	friend const BigInteger operator+(const BigInteger &a, const BigInteger &b);
	friend const BigInteger operator-(const BigInteger &a, const BigInteger &b);
	friend const BigInteger operator*(const BigInteger &a, const BigInteger &b);
	friend const BigInteger operator/(const BigInteger &a, int b);
	friend const BigInteger operator%(const BigInteger &a, int b);
	friend ostream& operator<<(ostream &out, const BigInteger &num);
	friend istream& operator>>(istream &in, BigInteger &num);

	BigInteger();
	BigInteger(int i);
	BigInteger(const char *str);
	void print() const;
	bool operator==(const BigInteger &other) const;
	bool operator!=(const BigInteger &other) const;
	bool operator<(const BigInteger &other) const;
	bool operator>(const BigInteger &other) const;
	bool operator<=(const BigInteger &other) const;
	bool operator>=(const BigInteger &other) const;
	BigInteger& operator+=(const BigInteger &other);
	BigInteger& operator-=(const BigInteger &other);
	BigInteger& operator*=(const BigInteger &other);
	BigInteger& operator/=(int val);
	BigInteger& operator%=(int val);
	BigInteger& operator++();
	const BigInteger operator++(int);
	BigInteger& operator--();
	const BigInteger operator--(int);
	void fromString(const char *str);
	void fromInt(int i);
	long long toLonglong() const;
	int toInt() const;

	BigInteger pow(unsigned int n);

	// return the remain number
	//
	int divideMe(int val);

	// the number of digits in 10-based BigInteger
	//
	unsigned int length() const;

private:
	void setZero();
	static int numCmp(const vector<int> &a1, const vector<int> &a2);
	static void removeHeadingZeros(vector<int> &vi);
	static void decreaseOne(vector<int> &vi);
	static void increaseOne(vector<int> &vi);

	// res add num, result puts on res
	//
	static void add(vector<int> &res, const vector<int> &other);

	// a minus b(a must be greater or equal than b), result puts on res
	// res may be a or b
	//
	static void minus(vector<int> &a, const vector<int> &b, vector<int> &res);

	// a /= b, return the remain number
	// though b is an unsigned integer but b should be in the range [1, 0x7FFFFFFF]
	//
	static unsigned int divide(vector<int> &a, unsigned int b);

private:
	mutable bool neg;
	vector<int> num;
};

BigInteger::BigInteger()
{
	setZero();
}
BigInteger::BigInteger(int i)
{
	fromInt(i);
}


BigInteger::BigInteger(const char *str)
{
	fromString(str);
}

void BigInteger::print() const
{
	if (neg)
		printf("-");
	for (int i = num.size() - 1; i >= 0; i--)
	{
		if (i != num.size() - 1)
			printf("%04d", num[i]);
		else
			printf("%d", num[i]);
	}
}

bool BigInteger::operator==(const BigInteger &other) const
{
	return (neg == other.neg && num == other.num);
}

bool BigInteger::operator!=(const BigInteger &other) const
{
	return !(*this == other);
}

bool BigInteger::operator<(const BigInteger &other) const
{
	if (neg != other.neg)
		return neg;
	int r = numCmp(num, other.num);
	if ((!neg && r < 0) || (neg && r > 0))
		return true;
	return false;
}

bool BigInteger::operator>(const BigInteger &other) const
{
	if (neg != other.neg)
		return !neg;
	int r = numCmp(num, other.num);
	if ((!neg && r > 0) || (neg && r < 0))
		return true;
	return false;
}

bool BigInteger::operator<=(const BigInteger &other) const
{
	if (neg != other.neg)
		return neg;
	int r = numCmp(num, other.num);
	if ((!neg && r <= 0) || (neg && r >= 0))
		return true;
	return false;
}

bool BigInteger::operator>=(const BigInteger &other) const
{
	if (neg != other.neg)
		return !neg;
	int r = numCmp(num, other.num);
	if ((!neg && r >= 0) || (neg && r <= 0))
		return true;
	return false;
}

BigInteger& BigInteger::operator+=(const BigInteger &other)
{
	if (neg == other.neg)
		add(num, other.num);
	else
	{
		int r = numCmp(num, other.num);
		if (r > 0)
			minus(num, other.num, num);
		else if (r < 0)
		{
			neg = !neg;
			minus(const_cast<vector<int> &>(other.num), num, num);
		}
		else
			setZero();
	}
	return *this;
}

BigInteger& BigInteger::operator-=(const BigInteger &other)
{
	if (neg != other.neg)
		add(num, other.num);
	else
	{
		int r = numCmp(num, other.num);
		if (r > 0)
			minus(num, other.num, num);
		else if (r < 0)
		{
			neg = !neg;
			minus(const_cast<vector<int> &>(other.num), num, num);
		}
		else
			setZero();
	}

	return *this;
}

BigInteger& BigInteger::operator*=(const BigInteger &other)
{
	BigInteger ans = *this * other;
	*this = ans;
	return *this;
}

BigInteger& BigInteger::operator/=(int val)
{
	divide(num, abs(val));
	if (neg ^ (val < 0) == 1 && !(num.size() == 1 && num[0] == 0))
		neg = true;
	else
		neg = false;
	return *this;
}


BigInteger& BigInteger::operator%=(int val)
{
	BigInteger ans = divide(num, abs(val));
	if (neg && !(ans.num.size() == 1 && ans.num[0] == 0))
		ans.neg = true;
	*this = ans;
	return *this;
}

BigInteger& BigInteger::operator++()
{
	if (!neg)
		increaseOne(num);
	else
	{
		decreaseOne(num);
		if (num.size() == 1 && num[0] == 0)
			neg = false;
	}
	return *this;
}

const BigInteger BigInteger::operator++(int)
{
	BigInteger tmp = *this;
	++(*this);
	return tmp;
}

BigInteger& BigInteger::operator--()
{
	if (neg)
		increaseOne(num);
	else
	{
		if (num.size() == 1 && num[0] == 0)
			neg = true;
		decreaseOne(num);
	}
	return *this;
}

const BigInteger BigInteger::operator--(int)
{
	BigInteger tmp = *this;
	--(*this);
	return tmp;
}

void BigInteger::fromInt(int i)
{
	if (i == 0)
		setZero();
	else
	{
		num.clear();
		neg = (i < 0);
		i = abs(i);
		while (i)
		{
			num.push_back(i % N);
			i /= N;
		}
	}
}

void BigInteger::fromString(const char *str)
{
	unsigned int len = strlen(str);
	if (len == 0)
		setZero();
	else
	{
		num.clear();
		int i = 0;
		if (str[i] == '-')
		{
			neg = true;
			i++;
		}
		else if (str[i] == '+')
		{
			neg = false;
			i++;
		}
		else
			neg = false;

		while (i < len - 1 && str[i] == '0')
			i++;

		unsigned int ans = 0;
		unsigned int mul = 1;
		for (int j = len - 1; j >= i; )
		{
			ans += (str[j] - '0') * mul;
			j--;
			mul *= 10;
			if (mul == 10000 || j < i)
			{
				mul = 1;
				num.push_back(ans);
				ans = 0;
			}
		}
	}
}

long long BigInteger::toLonglong() const
{
	long long ans = 0;
	for (int i = num.size() - 1; i >= 0; i--)
	{
		ans *= N;
		ans += num[i];
	}
	if (neg)
		ans = -ans;
	return ans;
}

int BigInteger::toInt() const
{
	int ans = 0;
	for (int i = num.size() - 1; i >= 0; i--)
	{
		ans *= N;
		ans += num[i];
	}
	if (neg)
		ans = -ans;
	return ans;
}


BigInteger BigInteger::pow(unsigned int n)
{
	if (n == 0)
		return BigInteger(1);
	if (n == 1)
		return *this;

	BigInteger tmp = pow(n >> 1);
	if ((n & 1) == 0)
		return tmp * tmp;
	else
		return tmp * tmp * (*this);
}

int BigInteger::divideMe(int val)
{
	int remain = divide(num, abs(val));

	if (neg ^ (val < 0) == 1 && !(num.size() == 1 && num[0] == 0))
		neg = true;
	else
		neg = false;

	if (neg && !(num.size() == 1 && num[0] == 0))
		remain = -remain;

	return remain;
}

unsigned int BigInteger::length() const
{
	unsigned int sz = num.size();
	unsigned int ans = sz * 4;
	if (num[sz - 1] < 1000)
		ans--;
	if (num[sz - 1] < 100)
		ans--;
	if (num[sz - 1] < 10)
		ans--;
	return ans;
}


void BigInteger::setZero()
{
	neg = false;
	num.clear();
	num.push_back(0);
}

int BigInteger::numCmp(const vector<int> &a1, const vector<int> &a2)
{
	if (a1.size() != a2.size())
		return a1.size() - a2.size();
	int s = a1.size();
	for (int i = s - 1; i >= 0; i--)
	{
		if (a1[i] != a2[i])
			return a1[i] - a2[i];
	}
	return 0;
}

void BigInteger::removeHeadingZeros(vector<int> &vi)
{
	int len = vi.size();
	for (int i = len - 1; i >= 1 && vi[i] == 0; i--)
		vi.pop_back();
}

void BigInteger::decreaseOne(vector<int> &vi)
{
	if (vi.size() == 1 && vi[0] == 0)
		vi[0] = 1;
	else
	{
		int carry = 1;
		for (unsigned int i = 0; i < vi.size(); i++)
		{
			vi[i] -= carry;
			if (vi[i] < 0)
			{
				vi[i] += N;
				carry = 1;
			}
			else
			{
				carry = 0;
				break;
			}
		}
		removeHeadingZeros(vi);
	}
}

void BigInteger::increaseOne(vector<int> &vi)
{
	int carry = 1;
	for (unsigned int i = 0; i < vi.size(); i++)
	{
		vi[i] += carry;
		if (vi[i] >= N)
		{
			vi[i] -= N;
			carry = 1;
		}
		else
		{
			carry = 0;
			break;
		}
	}
	if (carry)
		vi.push_back(1);
}


void BigInteger::add(vector<int> &res, const vector<int> &other)
{
	unsigned int p = max(res.size(), other.size());
	res.reserve(p + 1);
	unsigned int sum = 0;
	for (int i = 0; i < p; i++)
	{
		if (i >= res.size())
			res.push_back(0);
		sum += res[i];
		if (i < other.size())
			sum += other[i];
		if (sum >= N)
		{
			res[i] = sum - N;
			sum = 1;
		}
		else
		{
			res[i] = sum;
			sum = 0;
		}
	}
	if (sum)
		res.push_back(sum);
}

void BigInteger::minus(vector<int> &a, const vector<int> &b, vector<int> &res)
{
	int carry = 0;
	for (unsigned int i = 0; i < a.size(); i++)
	{
		int tmp = a[i];
		tmp -= carry;
		if (i < b.size())
			tmp -= b[i];
		if (tmp < 0)
		{
			tmp += N;
			carry = 1;
		}
		else
			carry = 0;
		if (i >= res.size())
			res.push_back(0);
		res[i] = tmp;
	}
	removeHeadingZeros(res);
}


unsigned int BigInteger::divide(vector<int> &a, unsigned int b)
{
	if (b == 0)
		throw exception("Divided by zero.");

	long long tmp = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	{
		tmp *= N;
		tmp += a[i];
		a[i] = tmp / b;
		tmp %= b;
	}
	removeHeadingZeros(a);
	return tmp;
}

const BigInteger operator+(const BigInteger &a, const BigInteger &b)
{
	return BigInteger(a) += b;
}

const BigInteger operator-(const BigInteger &a, const BigInteger &b)
{
	return BigInteger(a) -= b;
}

const BigInteger operator*(const BigInteger &a, const BigInteger &b)
{
	BigInteger ans;
	ans.num.reserve(a.num.size() + b.num.size());
	for (unsigned int i = 0; i < a.num.size(); i++)
	{
		int carry = 0;
		unsigned int j = 0;
		for (; j < b.num.size(); j++)
		{
			if (i + j >= ans.num.size())
				ans.num.push_back(0);
			int tmp = ans.num[i + j] + a.num[i] * b.num[j] + carry;
			if (tmp >= BigInteger::N)
			{
				carry = tmp / BigInteger::N;
				tmp %= BigInteger::N;
			}
			else
				carry = 0;
			ans.num[i + j] = tmp;
		}
		if (carry != 0)
		{
			if (i + j >= ans.num.size())
				ans.num.push_back(carry);
		}
	}
	if (a.neg == b.neg)
		ans.neg = false;
	else
		ans.neg = true;
	ans.removeHeadingZeros(ans.num);

	return ans;
}


const BigInteger operator/(const BigInteger &a, int b)
{
	BigInteger ans = a;
	ans /= b;
	return ans;
}

const BigInteger operator%(const BigInteger &a, int b)
{
	BigInteger ans = a;
	ans %= b;
	return ans;
}

ostream& operator<<(ostream &out, const BigInteger &num)
{
	num.print();
	return out;
}

istream& operator>>(istream &in, BigInteger &num)
{
	string str;
	if (in >> str)
		num.fromString(str.c_str());

	return in;
}


void testAddAssign()
{
	srand(time(0));
	for (int i = 0; i < 10000; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand() * rand();
		if (rand() & 1)
			r1 = -r1;
		if (rand() & 1)
			r2 = -r2;
		BigInteger bia(r1);
		BigInteger bib(r2);
		BigInteger biaa, bibb;
		BigInteger ans = bia + bib;
		biaa = bia;
		bibb = bib;
		bia += bib;
		bibb += biaa;
		assert(bia == bibb);
		assert(bia == ans);
		assert(bia.toLonglong() == (long long)r1 + r2);
	}
}

void testMinusAssign()
{
	srand(time(0));
	for (int i = 0; i < 10000; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand() * rand();
		if (rand() & 1)
			r1 = -r1;
		if (rand() & 1)
			r2 = -r2;
		BigInteger bia(r1);
		BigInteger bib(r2);
		BigInteger ans = bia - bib;
		bia -= bib;
		long long a1 = bia.toLonglong();
		long long a2 = (long long)r1 - r2;
		assert(a1 == a2);
		assert(ans == bia);
	}
}

void testMultiply()
{
	srand(time(0));
	for (int i = 0; i < 100; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand() * rand();
		BigInteger bia(r1);
		BigInteger bib(r2);
		BigInteger ans = bia * bib;
		long long a1 = ans.toLonglong();
		long long a2 = (long long)r1 * r2;
		assert(a1 == a2);
	}
}

void testDivide()
{
	srand(time(0));
	for (int i = 0; i < 100000; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand();
		if (r2 == 0)
			continue;

		if (rand() & 1)
			r1 = -r1;
		if (rand() & 1)
			r2 = -r2;

		BigInteger a(r1);
		BigInteger x = a / r2;
		int y = r1 / r2;
		if (x != y)
			int zz = 3;
		assert((a / r2) == (r1 / r2));
		r1 /= r2;
		a /= r2;
		assert(a == r1);
	}
}

void testMod()
{
	srand(time(0));
	for (int i = 0; i < 100000; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand();
		if (r2 == 0)
			continue;

		if (rand() & 1)
			r1 = -r1;
		if (rand() & 1)
			r2 = -r2;

		BigInteger a(r1);
		assert((a % r2) == (r1 % r2));
		r1 %= r2;
		a %= r2;
		assert(a == r1);
	}
}

void testCmp()
{
	for (int i = 0; i < 100; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand() * rand();
		BigInteger bia(r1);
		BigInteger bib(r2);
		assert((r1 < r2) == (bia < bib));
		assert((r1 <= r2) == (bia <= bib));
		assert((r1 > r2) == (bia > bib));
		assert((r1 >= r2) == (bia >= bib));
		assert((r1 == r2) == (bia == bib));
		assert((r1 != r2) == (bia != bib));
	}
	for (int i = 0; i < 100; i++)
	{
		int r1 = rand() * rand();
		int r2 = rand() * rand();
		if (rand() & 1)
		{
			r2 = r1;
		}
		BigInteger bia(r1);
		BigInteger bib(r2);
		assert((r1 < r2) == (bia < bib));
		assert((r1 <= r2) == (bia <= bib));
		assert((r1 > r2) == (bia > bib));
		assert((r1 >= r2) == (bia >= bib));
		assert((r1 == r2) == (bia == bib));
		assert((r1 != r2) == (bia != bib));
	}
}

void testIncDec()
{
	BigInteger a("-12345");
	int i = a.toInt();
	for (; i < 12345; a++, i++)
	{
		assert(a == i);
	}
	for (; i >= -12345; a--, i--)
	{
		assert(a == i);
	}
}

void testAddSelft()
{
	for (int i = 0; i < 100000; i++)
	{
		BigInteger a(i);
		int j = i;
		a += a;
		j += j;
		assert(a == j);

		BigInteger m(i);
		BigInteger n(i);
		m -= m;
		n -= n;
		assert(m == n);
	}
}
void testPow()
{
	BigInteger a(123);
	cout << a.pow(200);
}


int main()
{
	testMod();
	testDivide();
	testPow();
	testAddAssign();
	testMultiply();
	testCmp();
	testIncDec();
	testAddSelft();
	return 0;
}
